home *** CD-ROM | disk | FTP | other *** search
/ Chip 2000 October / CHIP Turkiye Ekim 2000.iso / prog / naps / 04 / setup.exe / Gnucleus / GnuHash.cpp < prev    next >
C/C++ Source or Header  |  2000-06-24  |  5KB  |  202 lines
  1. /********************************************************************************
  2.  
  3.     Gnucleus - A node application for the Gnutella network
  4.     Copyright (C) 2000 John Marshall
  5.  
  6.     This program is free software; you can redistribute it and/or modify
  7.     it under the terms of the GNU General Public License as published by
  8.     the Free Software Foundation; either version 2 of the License.
  9.  
  10.     This program is distributed in the hope that it will be useful,
  11.     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.     GNU General Public License for more details.
  14.  
  15.     You should have received a copy of the GNU General Public License
  16.     along with this program; if not, write to the Free Software
  17.     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  18.  
  19.     For support, questions, comments, etc...
  20.     E-Mail: 
  21.         swabby@c0re.net
  22.     
  23.     Address:
  24.         21 Cadogan Way
  25.         Nashua, NH, USA 03062
  26.  
  27. ********************************************************************************/
  28.  
  29. // GnuHash.cpp: implementation of the CGnuHash class.
  30. //
  31. //////////////////////////////////////////////////////////////////////
  32.  
  33. #include "stdafx.h"
  34. #include "Gnucleus.h"
  35. #include "GnucleusDoc.h"
  36.  
  37. #include "ViewSearch.h"
  38.  
  39. #include "GnuTransfer.h"
  40. #include "GnuSock.h"
  41. #include "GnuHash.h"
  42. #include "GnuControl.h"
  43.  
  44.  
  45. #ifdef _DEBUG
  46. #undef THIS_FILE
  47. static char THIS_FILE[]=__FILE__;
  48. #define new DEBUG_NEW
  49. #endif
  50.  
  51. //////////////////////////////////////////////////////////////////////
  52. // Construction/Destruction
  53. //////////////////////////////////////////////////////////////////////
  54.  
  55. CGnuHash::CGnuHash()
  56. {
  57.     GnuComm = NULL;
  58.     HashEntries = 0;
  59.     Current = 0;
  60.     Old = 1;
  61.  
  62.     for(int i = 0; i < HASH_SIZE; i++)
  63.     {
  64.         Table[0][i] = NULL;
  65.         Table[1][i] = NULL;
  66.     }
  67. }
  68.  
  69. CGnuHash::CGnuHash(CGnuControl *pGnuComm)
  70. {
  71.     GnuComm = pGnuComm;
  72.     HashEntries = 0;
  73.     Current = 0;
  74.     Old = 1;
  75.  
  76.     for(int i = 0; i < HASH_SIZE; i++)
  77.     {
  78.         Table[0][i] = NULL;
  79.         Table[1][i] = NULL;
  80.     }
  81. }
  82.  
  83. CGnuHash::~CGnuHash()
  84. {
  85.     for(int i = 0; i < HASH_SIZE; i++)
  86.     {
  87.         if(Table[0][i] != NULL)
  88.             delete Table[0][i];
  89.  
  90.         if(Table[1][i] != NULL)
  91.             delete Table[1][i];
  92.     }
  93. }
  94.  
  95. void CGnuHash::Insert(GUID *Guid, CGnuSock *Origin)
  96. {
  97.     DWORD key = CreateKey(Guid);
  98.     int attempts = MAX_REHASH;
  99.  
  100.     while(Table[Current][key] != NULL && attempts--)
  101.         key = (key + REHASH_VALUE) % HASH_SIZE;
  102.  
  103.     // Check to see if table is full
  104.     if(Table[Current][key] != NULL)  
  105.     {
  106.         // time to clean out the old and switch
  107.         ClearTable(Old);
  108.         if (Current == 0)
  109.         {
  110.             Current = 1;
  111.             Old = 0;
  112.         }
  113.         else
  114.         {
  115.             Current = 0;
  116.             Old = 1;
  117.         }
  118.         key = CreateKey(Guid); // don't need to rehash, we know it's empty
  119.     }
  120.  
  121.     Table[Current][key] = new key_data;
  122.     Table[Current][key]->Guid = *Guid;
  123.     Table[Current][key]->Origin = Origin;
  124.     HashEntries++;
  125. }
  126.  
  127. key_data* CGnuHash::FindValue(GUID *Guid)
  128. {    
  129.     DWORD key = CreateKey(Guid);
  130.     int attempts = MAX_REHASH;  // HASH_SIZE, I dont want to search forever
  131.  
  132.     // search the current table
  133.     while(attempts--)
  134.     {
  135.         if(Table[Current][key] != NULL && CompareGuid(&Table[Current][key]->Guid, Guid))
  136.             return Table[Current][key];
  137.  
  138.         key = (key + REHASH_VALUE) % HASH_SIZE;
  139.     }
  140.  
  141.     // try the old table
  142.     attempts = MAX_REHASH;
  143.     while(attempts--)
  144.     {
  145.         if(Table[Old][key] != NULL && CompareGuid(&Table[Old][key]->Guid, Guid))
  146.             return Table[Old][key];
  147.  
  148.         key = (key + REHASH_VALUE) % HASH_SIZE;
  149.     }
  150.  
  151.     // not found ...
  152.     return NULL;
  153. }
  154.  
  155. bool CGnuHash::CheckEmpty(int which)
  156. {
  157.     for(int i = 0; i < HASH_SIZE; i++)
  158.         if(Table[which][i] != NULL)
  159.             return 0;
  160.  
  161.     return 1;
  162. }
  163.  
  164. DWORD CGnuHash::CreateKey(GUID *Guid)
  165. {
  166.     byte *GuidRaw = (byte *) Guid;
  167.  
  168.     // XOR every 4 bytes together ...
  169.     DWORD key =  (GuidRaw[0] ^ GuidRaw[4] ^ GuidRaw[8] ^ GuidRaw[12]) +
  170.                 256 * (GuidRaw[1] ^ GuidRaw[5] ^ GuidRaw[9] ^ GuidRaw[13]) +
  171.                 256 * 256 * (GuidRaw[2] ^ GuidRaw[6] ^ GuidRaw[10] ^ GuidRaw[14]) +
  172.                 256 * 256 * 256 * (GuidRaw[3] ^ GuidRaw[7] ^ GuidRaw[11] ^ GuidRaw[15]);
  173.  
  174.     // and modulo it down to size
  175.     key %= HASH_SIZE;
  176.  
  177.     return key;
  178. }
  179.  
  180. bool CGnuHash::CompareGuid(GUID *Guid1, GUID *Guid2)
  181. {
  182.     byte *GuidRaw1 = (byte *) Guid1;
  183.     byte *GuidRaw2 = (byte *) Guid2;
  184.  
  185.     for(int i = 0; i < 16; i++)
  186.         if(GuidRaw1[i] != GuidRaw2[i])
  187.             return 0;
  188.  
  189.     return 1;
  190. }
  191.  
  192. void CGnuHash::ClearTable(int which)
  193. {
  194.     for(int i = 0; i < HASH_SIZE; i++)
  195.         if(Table[which][i] != NULL)
  196.         {
  197.             delete Table[which][i];
  198.             Table[which][i] = NULL;
  199.         }
  200.  
  201.     HashEntries = 0;
  202. }